package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //括号生成
        class Solution {
            List<String> ret;
            StringBuffer path;
            int right;
            int left;
            int n;

            public List<String> generateParenthesis(int length) {
                ret = new ArrayList<>();
                path = new StringBuffer();
                right = 0;
                left = 0;
                n = length;

                dfs();
                return ret;
            }

            // 回溯 + 约束剪枝
            public void dfs() {
                // 长度到达 2n，说明一定 left == right == n
                if (path.length() == 2 * n) {
                    ret.add(path.toString());
                    return;
                }

                // 还能放左括号
                if (left < n) {
                    path.append('(');
                    left++;
                    dfs();
                    left--; // 回溯：计数器恢复
                    path.deleteCharAt(path.length() - 1); // 回溯：删除最后一个字符
                }

                // 右括号必须比左括号少才能放
                if (right < left) {
                    path.append(')');
                    right++;
                    dfs();
                    right--; // 回溯：计数器恢复
                    path.deleteCharAt(path.length() - 1); // 回溯：删除最后一个字符
                }
            }
        }

        //组合
        class Solution2 {
            List<List<Integer>> ret;
            List<Integer> path;
            int n;
            int k;

            public List<List<Integer>> combine(int _n, int _k) {
                ret = new ArrayList<>();
                path = new ArrayList<>();
                k = _k;
                n = _n;

                dfs(1);
                return ret;
            }

            public void dfs(int key) {
                // 长度剪枝：选满即收集并返回，阻断无意义扩展
                if (path.size() == k) {
                    ret.add(new ArrayList<>(path));
                    return;
                }

                // 容量剪枝：当前层起点至多到 n - (还需数量) + 1
                int maxStart = n - (k - path.size()) + 1;

                for (int i = key; i <= maxStart; i++) {
                    path.add(i);
                    dfs(i + 1);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
}